SHIFT, REDUCE, ACCEPT, ERROR = range(4)

class Symbol:
    def __init__(self, name, terminal=False):
        self.terminal = terminal
        self.name = name[:]
        
    def __eq__(self, symbol):
        return self.name == symbol.name
    
    def __str__(self):
        return self.name
    
    def __hash__(self):
        return hash( self.name )

class TSymbol(Symbol):
    def __init__(self, name):
        Symbol.__init__(self, name, True)

class NTSymbol(Symbol):
    def __init__(self, name):
        Symbol.__init__(self, name, False)

SOS = TSymbol('$')
EOS = TSymbol('^')

class Production:
    def __init__(self, leftpart, rightpart, action = 'None'):
        self._leftpart = leftpart
        self._rightpart = rightpart
        self._action = action

    def setEnvVars(self, vars):
        self._envVars = vars
        
    def getLeftPart(self):
        return self._leftpart

    def getRightPart(self):
        return self._rightpart

    def getReduceLen(self):
        return len(self._rightpart)
    
    def reduce(self, reducedtokens, line = None):
        reducedsymblos = map(lambda x : x[0], reducedtokens)
        reducedattrs   = map(lambda x : x[1], reducedtokens)

        assert(reducedsymblos == self._rightpart)
        newattr = None
        if type(self._action) == str:
            print 'Calculating attribute'
            print '\tfunction:', self._action
            print '\targuments:', reducedattrs

            d = self._envVars

            d['tetragen'].setLine(line)
            d['a0'] = None
            for i in range(len(reducedattrs)):
                d['a%s' % (i+1)] = reducedattrs[i]
            exec(self._action, d)
            if 'a0' in d.keys():
                newattr = d['a0']
            else:
                newattr = None
        else:
            print 'Calculating attribute (unknown function)'
            newattr = self._action(reducedattrs)
        print '\tresult:', str(newattr)

        return self._leftpart, newattr

    def __eq__(self, other):
        if self._leftpart == other._leftpart and self._rightpart == other._rightpart:
            assert(self._action == other._action)
            return True
        return False

    def __str__(self):
        rpart = map(str, self._rightpart)
        rpartstr = reduce(lambda x, y: x + ' ' + y, rpart)
        return '%s -> %s (%s)' % (self._leftpart, rpartstr, self._action)
    
class Precedence:
    def __init__(self):
        self.less = False
        self.more = False
        self.equals = False
    
    def __str__(self):
        r = ""
        
        if self.less:
            r = r + "<"
        
        if self.more:
            r = r + ">"
        
        if self.equals:
            r = r + "="
            
        return r
    
class Grammar:
    
    EQUALS, LESS, MORE = xrange(3)
    
    def __init__(self):
        self.productions = []

    def addCode(self, code):
        d = {}
        for c in code:
            exec(c, d)

        self._envVars = {}
        if d['nameList']:
            for n in d['nameList']:
                self._envVars[n] = d[n]

    def addProduction(self, production):
        production.setEnvVars(self._envVars)
        self.productions.append(production)
    
    def _setPrecedenceElement(self, matrix, s1, s2, t):
        if not matrix.has_key(s1):
            matrix[s1] = {}
        
        if not matrix[s1].has_key(s2):
            matrix[s1][s2] = Precedence()
            
        if t == self.EQUALS:
            matrix[s1][s2].equals = True
            
        if t == self.LESS:
            matrix[s1][s2].less = True

        if t == self.MORE:
            matrix[s1][s2].more = True
            
        is_bad_precedence = (matrix[s1][s2].more and matrix[s1][s2].less) or (matrix[s1][s2].more and matrix[s1][s2].equals)
        if is_bad_precedence:
            print 'Precedence conflict: ', str(s1), matrix[s1][s2], str(s2)
        
    def _processProduction(self, m, p):
        if len(p.getRightPart()) == 1:
            return # one symbol in production
        
        for i in xrange(1, len(p.getRightPart())):
            current = p.getRightPart()[i]
            prev    = p.getRightPart()[i-1]
            #print "EQUALS", p.right[i-1], p.right[i]
            self._setPrecedenceElement(m, prev, current, self.EQUALS)
            
            for f in self.first(current, kleene=False):
                #print "LESS", p.right[i-1], f
                self._setPrecedenceElement(m, prev, f, self.LESS)
                
            for l in self.first(prev, False, kleene=False):
                for r in self.first(current):
                    if not r.terminal:
                        continue
                    
                    #print "MORE", l, r 
                    self._setPrecedenceElement(m, l, r, self.MORE)
        
    def getPrecedenceMatrix(self, start):
        m = {}
        
        for x in self.first(start, prefix=True, kleene=False):
            self._setPrecedenceElement(m, SOS, x, self.LESS)
            
        for x in self.first(start, prefix=False, kleene=False):
            self._setPrecedenceElement(m, x, EOS, self.MORE)
        
        for p in self.productions:
            self._processProduction(m, p)
            
        return m
    
    def first(self, nonterm, prefix = True, kleene = True): # Kleene closure is *
        pool = [nonterm]
        reached = []
        while True:
            iterated_reach = []
            for nt in pool:
                local = self._find_reachable(nt, prefix, kleene)
                pool.extend(local)
                pool = list(set(pool))[:]
                iterated_reach.extend(local)
            if set(iterated_reach) == set(reached):
                break
            else:
                reached.extend(iterated_reach)
                reached = list(set(reached))
                
        return reached

    def _find_reachable(self, nonterm, prefix, kleene):
        if nonterm.terminal:
            if kleene:
                return [nonterm]
            else:
                return []
        
        r = []
        
        for p in self.productions:
            if p.getLeftPart() == nonterm:
                if prefix:
                    r.append( p.getRightPart()[0] )
                else:
                    r.append( p.getRightPart()[-1] )
        return r

    def f(self, stackTop, nextToken):
        if nextToken == EOS and stackTop == self.startSymbol:
            return ACCEPT

        prec = None
        if stackTop in self.precedence.keys():
            if nextToken in self.precedence[stackTop].keys():
                prec = self.precedence[stackTop][nextToken]
            else:
                raise RuntimeError('Cant find lexer next: %s' % nextToken)
        else:
            raise RuntimeError('Cant find stack top: %s' % stackTop)

        if (prec.less and prec.more):
            raise RuntimeError('More and Less: %s, %s', str(stackTop), str(nextToken))

        if prec.less or prec.equals:
            return SHIFT
        
        if prec.more:
            return REDUCE

        return ERROR

    def g(self, stack):
        sprods = sorted(self.productions, lambda x, y : cmp(y.getReduceLen(), x.getReduceLen()))
        for prod in sprods:
            rlen = prod.getReduceLen()
            if len(stack) < rlen:
                continue
            if stack[-rlen:] == prod.getRightPart():
                return prod
        return None

    def build(self, start):
        self.startSymbol = start
        self.precedence = self.getPrecedenceMatrix(start)
